The present invention relates to digital signal processing, and more particularly, to high speed multiplying and adding circuits.
A number of digital signal processing techniques require the summing of a large number of products. Examples are convolutions, discrete Fourier transforms, and transversal filters. Each of these techniques involves sequences of numbers. For example, convolution is used to characterize linear sampled data systems. Convolution of two sequences r and s to obtain a third sequence c is defined as follows: ##EQU1##
In practical applications of Algorithm No. 1, r(k) and s(k) are zero, except for a finite number of terms N. Therefore, in digital processing circuitry for carrying out the convolution, the time required to perform the computation is a function of the size of N.
The discrete Fourier transform of a sequence r, denoted R(.omega.), is defined as follows: ##EQU2## where .omega. is in radians. In practical applications, only a finite number of r(n)'s are non-zero and the sequence r represents samples of a function which is continuous with respect to time. Under these conditions, the discrete Fourier transform gives the frequency context of the samples.
A transversal (non-recursive) filter is a device whose input is a sequence x and whose output is a sequence y given by: ##EQU3## Such filters are used to replace analog R-C filters in sampled data systems.
In Formulas 1, 2 and 3 above, it is necessary to compute the dot product of two vectors A=(a(1), . . . ,a(N)) and B=(b(1), . . . ,b(N)) where: ##EQU4##
Conventionally, the dot product of the vectors A and B (Algorithm No. 4) is computed by sequentially multiplying the components of A and B together and adding the same. On a general purpose digital computer this involves programming a loop. The time required to compute the dot product of the vectors A and B is a linear function of the size of N. Substantial computational delays can result if N is large. If the vector B is held fixed in Algorithm No. 4, the computational delay becomes even more pronounced. It would be desirable to provide a digital system for rapidly calculating the dot product of vectors A and B for large values of N.
Heretofore digital systems have been provided for multiplying and adding at high speeds. See for example U.S. Pat. Nos. 4,369,500; 4,153,938; 4,142,242; 4,135,249; 4,031,377; 3,752,971; 3,691,359; 3,670,956; 3,372,269 and 3,163,749. However, all of these patents describe circuits which perform multiple multiplications serially, thereby inherently limiting the speed at which the dot product of large dimensional vectors can be calculated. See also A. Weinberger, "Multiplier Decoding with Look-Ahead", IBM Technical Disclosure Bulletin, Vol. 20, No. 9, February, 1978, pp. 3591-3593 and T. Jayashree and D. Basu, "On Binary Multiplication Using Quarter Square Algorithm", IEEE Transactions on Computers, September, 1976, pp. 957-960.